package com.ghh.algorithm;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author hgu
 * 
 */
public class BinaryTreeSort {
	public Integer[] sort(Integer[] d) {
		int len = d.length;
		if (len <= 1) {
			return d;
		}
		System.out.println("//sort" + Arrays.toString(d));
		int m = len / 2;
		int node = d[m];
		Integer[] l = new Integer[len];
		Integer[] r = new Integer[len];
		int ll = 0;
		int lr = 0;
		for (int i = 0; i < len; i++) {
			if (i == m) {
				continue;
			}
			if (d[i] <= node) {
				l[ll] = d[i];
				ll++;
			} else {
				r[lr] = d[i];
				lr++;
			}
		}
		if (ll > 0) {
			System.arraycopy(sort(Arrays.copyOfRange(l, 0, ll)), 0, d, 0, ll);
		}
		d[ll] = node;
		if (lr > 0) {
			System.arraycopy(sort(Arrays.copyOfRange(r, 0, lr)), 0, d, ll + 1, lr);
		}
		System.out.println(Arrays.toString(d));
		return d;
	}

	public static void main(String[] args) {
		BinaryTreeSort ts = new BinaryTreeSort();
		Integer[] ai = new Integer[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
		List<Integer> il = Arrays.asList(ai);
		Collections.shuffle(il);
		Integer[] s = ts.sort(il.toArray(new Integer[ai.length]));
		System.out.println(Arrays.toString(s));
	}
}
